package com.mjlf.algorithms.sort;

/**
 * @auther a123
 * @create 2018-09-05 20:24
 * @desc 插入排序
 * 插入排序， 有点像平时玩扑克的时候整理拍一样，每次从一端取出一张，然后在已经排好序牌中找一个合适的位置插入
 * 这种排序取决于输入的顺序，如果输入够理想，排序效率是很好的
 *
 * 比较次数：最坏为 n * n / 2, 数据移动次数为：n * n / 2
 *          最好的情况：n 数据移动次数 n
 */
public class InsertSort {

    public static void main(String[] args){
        Integer[] elements = {2, 1, 1, 1, 1, 1, 1};
        sortFromIndex(elements);
        SortUtil.show(elements);
    }

    /**
     * 使用每次从最后去一个元素与最前面排好序的元素比较，然后查找合适的位置， 在将这个位置后的元素向后平移
     * @param elements
     */
    public static void sortFromLast(Comparable[] elements){
        int len = 0;
        while(len < elements.length){
            //每次去最后一个元素
            Comparable e = elements[elements.length - 1];

            //最后一个元素应有的位置
            int index = len;
            for(int i = 0; i < len ; i++){//查找合适的位置
                if(SortUtil.less(e, elements[i])){
                    index = i;
                    break;
                }
            }

            //移动元素
            for(int i = elements.length - 1; i > index; i --){
                elements[i] = elements[i - 1];
            }

            //在应有的位置插入最后一个元素
            elements[index] = e;
            len ++;
        }
    }

    /**
     * 同样的插入排序，这种只需要5行就可以解决，而且效率比上边那最后那种还好点
     * 思路：
     * 从前向后依次排序，第一次去0位置与前边的每个元素比较， 如果小则被比较元素向后移动，第二次，第三次分别去1， 2 位置与前边依次比较
     * 我们要考虑的更一般的情况是部分有序的数组。倒置指的是数组中的两个顺序颠倒的元素。比 如 E X A M P L E 中有 11 对倒置:
     * E-A、 X-A、 X-M、 X-P、 X-L、 X-E、 M-L、 M-E、 P-L、 P-E 以及 L-E。如果数组中倒置的数量小于数组大小的某个倍数，
     * 那么我们说这个数组是部分有序的。 下面是几种典型的部分有序的数组
     *
     * 插入排序的交换吃等于倒置次数，比较次数大于等于倒置次数，小于等于倒置次数 + N -1
     *
     * 证明：每次交换都会少一个倒置，当倒置数量为0时，表示排序完成
     * 每次交换都对应着一次比较，且 1 到 N-1 之间的每个 i 都可能需要一次 额外的比较(在 a[i] 没有达到数组的左端时)
     *
     * @param element
     */
    public static void sortFromIndex(Comparable[] element){
        for(int i = 0; i < element.length; i ++){
            Comparable indexElement = element[i];
            for(int j = i - 1; j >= 0 && SortUtil.less(indexElement, element[j]); j --){
                SortUtil.exch(element, j + 1, j);
            }
        }
    }

    /**
     * 优化后的插入排序，下边这种在交换的时候只是将原始向后移动，并不是进行交换，这样可以省掉大约2/3的赋值次数
     *
     * 实验表明，插入排序速度基本比选着排序快一倍
     * @param element
     */
    public static void sortFromIndexTuring(Comparable[] element){
        for(int i = 0; i < element.length; i ++){
            Comparable indexElement = element[i];
            int j = i -1;
            for(; j >= 0 && SortUtil.less(indexElement, element[j]); j --){
                element[j + 1] = element[j];
            }
            element[j + 1] = indexElement;
        }
    }
}
